﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace AlgorithmCenter
{
    public class AlgorithmCenter200721
    {
        /// <summary>
        /// 贪心策略解决硬币问题
        /// </summary>
        /// <param name="everyCoinsNum"></param>
        /// <param name="totalMoney"></param>
        /// <returns></returns>
        public int MinimumNumOfCoins(Dictionary<int,int> everyCoinsNum,int totalMoney)
        {
            int sum = 0;          
            
            foreach (int theCoinsDenomination in everyCoinsNum.Keys)
            {
                //需要当前面额的总数量
                int needThisCoinsNum = (totalMoney / theCoinsDenomination);
                //获取当前面额的数量
                everyCoinsNum.TryGetValue(theCoinsDenomination,out int nums);
                //判断需要当前面额数量和当前面额所具有数量的大小
                if (needThisCoinsNum > nums)
                {
                    sum += nums;
                    totalMoney -= theCoinsDenomination*nums;
                }
                else
                {
                    sum += needThisCoinsNum;
                    //获取剩余的钱数
                    if (nums > 0)
                        totalMoney %= theCoinsDenomination;
                }
                
            }
            return totalMoney>0?sum+1:sum;
        }

        /// <summary>
        /// 贪心策略解决木板截取最小开销问题，类哈夫曼编码问题
        /// </summary>
        /// <param name="n"></param>
        /// <param name="everyChildBoardLen"></param>
        /// <returns></returns>
        public int CaluateMinSpendInCutBoard(int n,int[] everyChildBoardLen)
        {
            int spends = 0;
            int maxSpends = 0;
            foreach (int i in everyChildBoardLen)
            {
                maxSpends += i;
            }

            while (true)
            {
                //获取数组中最小的两个木板的下标
                GetMinNumAndSecondMinNumIndex(everyChildBoardLen,out int minNumIndex,out int secondMinNumIndex);
                //计算这两个木板的开销
                int tempSpends=everyChildBoardLen[minNumIndex] + everyChildBoardLen[secondMinNumIndex];
                //将开销加入到总开销中
                spends += tempSpends;
                everyChildBoardLen[minNumIndex] = tempSpends;
                //这里将已经遍历过的其中一个数标记成-1（达到删除的状态）
                everyChildBoardLen[secondMinNumIndex] = int.MaxValue;
                if (tempSpends == maxSpends)
                    break;
            }
            return spends;
        }
        /// <summary>
        /// 获取数组最小和次小的数据(至少有两个数)
        /// </summary>
        /// <param name="a"></param>
        /// <param name="minNum"></param>
        /// <param name="secondMinNum"></param>
        public void GetMinNumAndSecondMinNumIndex(int[] a,out int minNumIndex,out int secondMinNumIndex)
        {
            minNumIndex = a[0]>a[1]?1:0;
            secondMinNumIndex = a[0] > a[1] ? 0 : 1;

            for (int i=2;i<a.Length;i++)
            {
                if (a[i]!=int.MaxValue)
                {
                    if (a[i] < a[minNumIndex])
                    {
                        secondMinNumIndex = minNumIndex;
                        minNumIndex = i;
                    }
                    else if(a[i]<a[secondMinNumIndex])
                    {
                        secondMinNumIndex = i;
                    }
                    
                }
            }
           
        }
    }
}
